|
泛型编程：源起、实现与意义
泛型编程：源起、实现与意义
By 刘未鹏
C++的罗浮宫(http://blog.csdn.net/pongba)
(去年12月《程序员》的约稿)
(以前也写过一篇相关的文章：Generic Programming - What Are You, anyway? )
为什么泛型
泛型编程（Generic Programming）最初提出时的动机很简单直接：发明一种语言机制，能够帮助实现一个通用的标准容器库。所谓通用的标准容器库，就是要能够做到，比如用一个List类存放所有可能类型的对象,这样的事情；熟悉一些其它面向对象的语言的人应该知道，如Java里面这是通过在List里面存放Object引用来实现的。Java的单根继承在这里起到了关键的作用。然而单根继承对C++这样的处在语言链底层的语言却是不能承受之重。此外使用单根继承来实现通用容器也会带来效率和类型安全方面的问题，两者都与C++的理念不相吻合。
于是C++另谋他法——除了单根继承之外，另一个实现通用容器的方案就是使用“参数化类型”。一个容器需要能够存放任何类型的对象，那干脆就把这个对象的类型“抽”出来，参数化它[1]：
template class vector {
T* v;
int sz;
public:
vector(int);
T& operator[](int);
T& elem(int i) { return v[i]; }
// ...
};
一般来说看到这个定义的时候，每个人都会想到C的宏。的确，模板和宏在精神上的确有相仿之处。而且的确，也有人使用C的宏来实现通用容器。模板是将一个定义里面的类型参数化出来，而宏也可以做到参数化类型。甚至某种意义上可以说宏是模板的超集——因为宏不仅可以参数化类型，宏实质上可以参数化一切文本，因为它本来就是一个文本替换工具。然而，跟模板相比，宏的最大的缺点就是它并不工作在C++的语法解析层面，宏是由预处理器来处理的，而在预处理器的眼里没有C++，只有一堆文本，因此C++的类型检查根本不起作用。比如上面的定义如果用宏来实现，那么就算你传进去的T不是一个类型，预处理器也不会报错；只有等到文本替换完了，到C++编译器工作的时候才会发现一堆莫名其妙的类型错误，但那个时候错误就已经到处都是了。往往最后会抛出一堆吓人的编译错误。更何况宏基本无法调试。
注1
实际上，还有一种实现通用容器的办法。只不过它更糟糕：它要求任何能存放在容器内的类型都继承自一个NodeBase，NodeBase里面有pre和next指针，通过这种方式，就可以将任意类型链入一个链表内了。但这种方式的致命缺点是(1)它是侵入性的，每个能够放在该容器内的类型都必须继承自NodeBase基类。(2)它不支持基本内建类型（int、double等），因为内建类型并不，也不能继承自NodeBase。这还姑且不说它是类型不安全的，以及效率问题。
我们再来看一看通用算法，这是泛型的另一个动机。比如我们熟悉的C的qsort：
void qsort(void *base, size_t nmemb, size_t size,
int (*compar)(const void *, const void *));
这个算法有如下几个问题：
1. 类型安全性：使用者必须自行保证base指向的数组的元素类型和compar的两个参数的类型是一致的；使用者必须自行保证size必须是数组元素类型的大小。
2. 通用性：qsort对参数数组的二进制接口有严格要求——它必须是一个内存连续的数组。如果你实现了一个巧妙的、分段连续的自定义数组，就没法使用qsort了。
3. 接口直观性：如果你有一个数组char* arr = new arr[10];那么该数组的元素类型其实就已经“透露”了它自己的大小。然而qsort把数组的元素类型给“void”掉了（void *base），于是丢失掉了这一信息，而只能让调用方手动提供一个size。为什么要把数组类型声明为void*？因为除此之外别无它法，声明为任意一个类型的指针都不妥（compar的参数类型也是如此）。qsort为了通用性，把类型信息丢掉了，进而导致了必须用额外的参数来提供类型大小信息。在这个特定的算法里问题还不明显，毕竟只多一个size参数而已，但一旦涉及的类型信息多了起来，其接口的可伸缩性（scalability）问题和直观性问题就会逐渐显现。
4. 效率：compar是通过函数指针调用的，这带来了一定的开销。但跟上面的其它问题比起来这个问题还不是最严重的。
泛型编程
泛型编程最初诞生于C++中，由Alexander Stepanov[2]和David Musser[3]创立。目的是为了实现C++的STL（标准模板库）。其语言支持机制就是模板（Templates）。模板的精神其实很简单：参数化类型。换句话说，把一个原本特定于某个类型的算法或类当中的类型信息抽掉，抽出来做成模板参数T。比如qsort泛化之后就变成了：
template
void sort(RandomAccessIterator first, RandomAccessIterator last,
Compare comp);
其中first，last这一对迭代器代表一个前闭后开区间，迭代器和前开后闭区间都是STL的核心概念。迭代器建模的是内建指针的接口（解引用、递增、递减等）、前开后闭区间是一个简单的数学概念，表示从first（含first）到last（不含last）的区间内的所有元素。此外，comp是一个仿函数（functor）。仿函数也是STL的核心概念，仿函数是建模的内建函数的接口，一个仿函数可以是一个内建的函数，也可以是一个重载了operator()的类对象，只要是支持函数调用的语法形式就可成为一个仿函数。
通过操作符重载，C++允许了自定义类型具有跟内建类型同样的使用接口；又通过模板这样的参数化类型机制，C++允许了一个算法或类定义，能够利用这样的接口一致性来对自身进行泛化。例如，一个原本操作内建指针的算法，被泛化为操纵一切迭代器的算法。一个原本使用内建函数指针的算法，被泛化为能够接受一切重载了函数调用操作符（operator()）的类对象的算法。
让我们来看一看模板是如何解决上面所说的qsort的各个问题的：
1. 类型安全性：如果你调用std::sort(arr, arr + n, comp);那么comp的类型就必须要和arr的数组元素类型一致，否则编译器就会帮你检查出来。而且comp的参数类型再也不用const void*这种不直观的表示了，而是可以直接声明为对应的数组元素的类型。
2. 通用性：这个刚才已经说过了。泛型的核心目的之一就是通用性。std::sort可以用于一切迭代器，其compare函数可以是一切支持函数调用语法的对象。如果你想要将std::sort用在你自己的容器上的话，你只要定义一个自己的迭代器类（严格来说是一个随机访问迭代器，STL对迭代器的访问能力有一些分类，随机访问迭代器具有建模的内建指针的访问能力），如果需要的话，再定义一个自己的仿函数类即可。
3. 接口直观性：跟qsort相比，std::sort的使用接口上没有多余的东西，也没有不直观的size参数。一个有待排序的区间，一个代表比较标准的仿函数，仅此而已[4]。
4. 效率：如果你传给std::sort的compare函数是一个自定义了operator()的仿函数。那么编译器就能够利用类型信息，将对该仿函数的operatpr()调用直接内联。消除函数调用开销。
动态多态与静态多态
泛型编程的核心活动是抽象：将一个特定于某些类型的算法中那些类型无关的共性抽象出来，比如，在STL的概念体系里面，管你是一个数组还是一个链表，反正都是一个区间，这就是一层抽象。管你是一个内建函数还是一个自定义类，反正都是一个Callable（可调用）的对象（在C++里面通过仿函数来表示），这就是一层抽象。泛型编程的过程就是一个不断将这些抽象提升（lift）出来的过程，最终的目的是形成一个最大程度上通用的算法或类。
有人肯定会问，既然同是抽象，那为什么不用基于多态的面向对象抽象呢？比如STL的std::for_each，用Java的多态机制也可以解决：
interface IUnaryFun
{
void invoke(Object o);
}
interface IInputIter
{
IInputIter preIncrement();
boolean equals(IInputIter otherIter);
… // other methods
}
IUnaryFun for_each(IInputIter first, IInputIter last, IUnaryFun func)
{
for(;!first.equals(last); first.preIncrement())
func.invoke(*first);
return func;
}
其实，这里最主要的原因很简单，效率。面向对象的多态引入了间接调用。当然，并不是说间接调用不好，有些时候，比如确实需要运行期多态的时候，只能诉诸继承这样的手段。但当能够利用编译期类型信息的时候，为什么要付出不必要的间接调用开销呢？比如这里的for_each，利用接口来实现其通用性，就付出了所谓的“抽象惩罚”（abstraction penalty）。而C++的模板，就是为了消除这样的抽象惩罚。利用模板编写的std::for_each，对于每一个特定的参数类型组合都有一个独立的，最高效的实例化版本，就跟你手写一个特定于这些类型的专门的for_each算法一样[5]。于是抽象惩罚消失了，而这也正是C++模板库能够真正被工业界广泛用在C++最擅长的领域（重视效率的领域）的重要原因之一。
另一方面，对于每一组参数类型组合实例化一个版本出来的做法增加了代码空间，这是一个典型的以空间换时间的例子，不过对于一门静态并追求效率的语言来说，这个代码空间的开销反正也是必不可少的，因为即便你手动为各种不同的参数类型组合编写特定的算法版本的话，也是付出一样的代码空间开销，而且还顺便违反了DRY原则[6]。此外，由于在抽象的时候不用总想着要建立的接口，所以泛型算法编写起来也更为直观。
C++泛型的另一个好处就是，跟面向对象编程的基于继承和虚函数的运行时多态机制不同，C++模板是非侵入性的。你不需要让你的类继承自某个特定的接口才能用于某个算法，只要支持特定的语法接口就行了（比如只要支持begin()调用）。这也被称为结构一致性（Structural Conformance），意即只要语法结构一致即可。而另一方面，基于接口继承的面向对象多态则必须要显式地声明继承自一个接口，这就是所谓的名字一致性（Named Conformance）。
当然，泛型支持的静态多态和虚函数支持的动态多态并没有任何程度上绝对的优劣之分。它们适用于不同的场合。当类型信息可得的时候，利用编译期多态能够获得最大的效率和灵活性。当具体的类型信息不可得，就必须诉诸运行期多态了。Bjarne Stroustrup曾经用了一个典型的例子来澄清这个区别：
std::vector v;
… // fill v
std::for_each(v.begin(), v.end(), std::mem_fun(&Shape::draw));
这里，v里面到底将来会存放什么类型的Shape，编译期无法知道，因而必须求助于动态多态。另一方面，编译器倒的确知道它们都继承自Shape，利用这仅有的静态类型信息，我们使用了泛型算法std::for_each和泛型容器std::vector。这里尤其值得注意的是for_each的静态多态行为：for_each只有一份模板实现，然而根据传给它的第三个参数（本例中是std::mem_fun(&Shape::draw)）的不同，for_each的行为也不同（这里最终被for_each调用的是Shape::draw，但实际上你可以包装任何函数，只要这个函数接受一个Shape*型的参数），for_each这种“行为不同”是发生在编译期的，所以是静态多态。
前面说过，模板与接口继承比较，模板是非侵入的。这是C++泛型与面向对象的多态机制的本质区别之一。但实际上，面向对象未必就意味着一定要用接口来实现动态的多态。一些动态类型的脚本语言，如Ruby，它的多态机制就既是运行期（动态）的，又是非倾入性的（不用通过继承自某个特定的接口来达到复用）。人们把这个叫做Duck Typing[7]。如果不是因为效率问题，其实这样的多态机制才是最直观的，从使用方面来说，它既有非侵入性，又没有只能工作在编译期的限制。但效率至少在可见的将来、在某些领域仍是一个顾虑。因此像C++这种区分编译期和运行期多态的语言，仍有其独特的优势。
此外，泛型编程的类型安全优势也让它从C++走入了其它主流的静态类型语言当中，尤其是C家族的Java和C#，在前几年相继接纳泛型。
特化，图灵完备性，元编程
C++的模板是支持特化的，这就给了它实现编译期控制结构的可能性，进而带来了一个图灵完备的子语言。模板特化的引入原本只是为了效率目的——针对不同的类型提供不同的实现。但后来却被发现能够实现编译期的if/else和递归等控制结构。
模板元编程最初由Erwin Unruh在1994年的一次会议上提出；当时他写了一个程序，在编译错误里面打印出一个素数序列。这个事件在C++历史上的地位就仿佛哥伦布发现新大陆。用Bjarne Stroustrup的话来说就是当时他当时和其他几个人觉得太神奇了。实际上，这个事情正标志了C++模板系统的图灵完备性被发现；后来Todd Veldhuizen写了一篇paper，用C++模板构建了一个元图灵机，从而第一次系统证明了C++模板的图灵完备性。接下来的事情就顺理成章了——一些ad hoc的模板元编程技巧不断被发掘出来，用于建造高效、高适应性的通用组件。最终，David Abrahams编写了boost库中的基本组件之一：Boost.MPL库。Boost.MPL以类型和编译期常量为数据，以模板特化为手段，实现了一个编译期的STL。你可以看到常见的vector，你可以看到transform算法，只不过算法操纵的对象和容器存放的对象不再是运行期的变量或对象，而是编译期的类型和常量。想知道模板元编程是如何用在库构建中的，可以打开一个Boost的子库（比如Boost.Tuple或Boost.Variant）看一看。
然而，毕竟C++的模板元编程是一门被发现而不是被发明的子语言。一方面，它在构建泛型库的时候极其有用。然而另一方面，由于它并非语言设计初始时考虑在内的东西，所以不仅在语法上面显得不那么first-class（比较笨拙）；更重要的是，由于本不是一个first-class的语言特性，所以C++编译器并不知道C++元编程的存在。这就意味着，比如对下面这样一个编译期的if/else设施[8]：
template
struct if_ {
typedef X type; // use X if b is true
};
template
struct if_ {
typedef Y type; // use Y if b is false
};
typedef if_ |